package backtracing;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: june
 * @date: 2023/7/26
 * @description: 17. 电话号码的字母组合
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 **/

public class LetterCombinations_17 {

    // 记录数字与字母的映射关系，双括号初始化map，匿名内部类，java8新特性
    Map<Character, String> charMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        backtrace(digits, 0);
        return result;
    }

    /**
     * 回溯法
     *
     * @param digits 原来的数字组合
     * @param index  数字组合中的数字的索引，取值范围[0, digits.length()-1]
     */
    private void backtrace(String digits, int index) {
        // 当index与数字组合的大小相等，说明已经得到了需要的字母组合
        if (index == digits.length()) {
            result.add(sb.toString());
            return;
        }

        char ch = digits.charAt(index);
        for (char c : charMap.get(ch).toCharArray()) {
            sb.append(c);
            backtrace(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        List<String> strings = new LetterCombinations_17().letterCombinations("23");
        System.out.println(strings);
    }
}
